package com.nl.trees;

import com.nl.trees.BTree.Node;

public class TreeDepth {

	//计算树的高度
	public static<T> int getDepth(BTree<T> tree){
		if(tree!=null){
			return getDepth(tree.root);
		}
		return 0;
	}

	public static<T> int getDepth(Node<T> proot){
		if(proot == null){
			return 0;
		}
		int left = getDepth(proot.left);
		int right = getDepth(proot.right);
		int max = left >right ?left:right;
		return max+1;
	}
	
	//树是不是平衡的
	public static<T> boolean isBalance(Node<T> proot){
		if(proot==null){
			return true;
		}
		int left = getDepth(proot.left);
		int right = getDepth(proot.right);
		if(Math.abs(left-right) >1){
			return false;
		}
		return isBalance(proot.left)&&isBalance(proot.right);
	}
	public static class Depth{
		int depth;
		public Depth(){
			this.depth =0;
		}
	}
	//树是不是平衡的
	public static<T> boolean isBalance2(Node<T>proot){
		Depth depth = new Depth();
		return isBalance2(proot, depth);
	}
	public static<T> boolean isBalance2(Node<T> proot,Depth depth){
		if(proot==null){
			depth.depth =0;
			return true;
		}
		Depth left = new Depth();
		Depth right= new Depth();
		//先遍历左右子树，记录树的深度，减少重复计算的次数
		if(isBalance2(proot.left, left)&& isBalance2(proot.right, right)){
			if(Math.abs(left.depth-right.depth)<=1){
				depth.depth = 1+(left.depth>right.depth?left.depth:right.depth);
				return true;
			}
		}
		return false;
	}
}
